package own.stu.jobgib.playown.alg.leetcode.editor.cn.demo;

import java.util.*;
import java.util.stream.Collectors;

public class Demo_2 {
    public static void main(String[] args) {

//        System.out.println(trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
//        System.out.println(removeKdigits("1432219", 3));

//        System.out.println(removeDuplicates("abcd", 4));
//        System.out.println(removeDuplicates("deeedbbcccbdaa", 3));

//        System.out.println(minOperations(new String[]{"d1/","d2/","../","d21/","./"}));
//        System.out.println(minOperations(new String[]{"d1/","d2/","./","d3/","../","d31/"}));

//        System.out.println(maximumGain("cdbcbbaaabab", 4, 5));

//        System.out.println(countStudents(new int[]{1,1,1,0,0,1}, new int[]{1,0,0,0,1,1}));

        /*RecentCounter r = new RecentCounter();
        System.out.println(r.ping(1));
        System.out.println(r.ping(100));
        System.out.println(r.ping(3001));
        System.out.println(r.ping(3002));*/

//        System.out.println(removeDuplicates("abbaca"));
//        System.out.println(removeDuplicates("azxxzy"));

//        System.out.println(maxVowels("abciiidef", 3));
//        System.out.println(maxVowels("leetcode", 3));
//        System.out.println(maxVowels("aeiou", 2));
//        System.out.println(maxVowels("tryhard", 4));
//        System.out.println(maxVowels("novowels", 1));

//        System.out.println(findMaxAverage(new int[]{0, 4, 0, 3, 2}, 1));
//        Arrays.stream(getAverages(new int[]{7,4,3,9,1,8,5,2,6}, 3)).forEach(System.out::println);
//        Arrays.stream(getAverages(new int[]{}, 40000)).forEach(System.out::println);

//        System.out.println(maxSum(Arrays.asList(1,1,1,3), 2, 2));
//        System.out.println(maxSum(Arrays.asList(1,2,2), 2, 2));

//        System.out.println(maxScore(new int[]{1,2,3,4,5,6,1}, 3));

//        System.out.println(lengthOfLongestSubstring("abcabcbb"));

//        System.out.println(longestSubarray(new int[]{1,1,0,1}));
//        System.out.println(longestSubarray(new int[]{0, 1, 1, 1, 0, 1, 1, 0, 1}));
//        System.out.println(longestSubarray(new int[]{1, 1, 1}));

//        System.out.println(equalSubstring("abcd", "bcdf", 3));
//        System.out.println(equalSubstring("anryddgaqpjdw", "zjhotgdlmadcf", 5));

//        System.out.println(totalFruit(new int[]{1,2,1}));
//        System.out.println(totalFruit(new int[]{0,1,2,2}));
//        System.out.println(totalFruit(new int[]{1,2,3,2,2}));
//        System.out.println(totalFruit(new int[]{3,3,3,1,2,1,1,2,3,3,4}));


//        System.out.println(maximumUniqueSubarray(new int[]{4, 2, 4, 5, 6}));
//        System.out.println(maximumUniqueSubarray(new int[]{5, 2, 1, 2, 5, 2, 1, 2, 5}));

//        System.out.println(longestOnes(new int[]{1,1,1,0,0,0,1,1,1,1,0}, 2));

//        System.out.println(minOperations(new int[]{3,2,20,1,1,3}, 10));

        /*System.out.println("xxx".compareTo("xxxa"));
        System.out.println("xxx".compareTo("xxy"));
        System.out.println("xxx".compareTo("xxa"));*/

        /*System.out.println(balancedString("QQWE"));
        System.out.println(balancedString("QQQE"));*/

//        System.out.println(minSizeSubarray(new int[]{1,2,3}, 5));
//        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
//        System.out.println(minWindow("a", "a"));

        /*System.out.println(getNums(2));
        System.out.println(getNums(3));
        System.out.println(getNums(6));*/

//        System.out.println(numSubarrayProductLessThanK(new int[]{10,5,2,6}, 100));
//        System.out.println(numSubarrayProductLessThanK(new int[]{57,44,92,28,66,60,37,33,52,38,29,76,8,75,22}, 18));
//        System.out.println(numSubarrayProductLessThanK(new int[]{1,1,1}, 1));

//        System.out.println(countKConstraintSubstrings("10101", 1));

//        System.out.println(continuousSubarrays(new int[]{5,4,2,4}));
//        System.out.println(continuousSubarrays(new int[]{1,2,3}));
//        System.out.println(continuousSubarrays(new int[]{65,66,67,66,66,65,64,65,65,64}));
//        System.out.println(continuousSubarrays(new int[]{6,4,5,3,2}));

//        System.out.println(countGood(new int[]{1,1,1,1,1}, 10));

//        System.out.println(numSubarraysWithSum(new int[]{0,0,0,0,0}, 0));

//        System.out.println(countOfSubstrings("aeioqq", 1));
//        System.out.println(countOfSubstrings("ieaouqqieaouqq", 1));

//        System.out.println(longestNiceSubarray(new int[]{1, 3, 8, 48, 10}));

//        System.out.println(maxRepOpt1("aaabaaa"));

//        System.out.println(characterReplacement("ABAA", 0));
//        System.out.println(characterReplacement("ABBB", 2));

//        System.out.println(findAnagrams("cbaebabacd", "abc"));

        int[][] ints = fileCombination(18);
        for (int[] anInt : ints) {
            Arrays.stream(anInt).forEach(System.out::print);
            System.out.println();
        }
    }

    public static int[][] fileCombination(int target) {
        if (target < 2) {
            return new int[][]{};
        }
        int right = target / 2 + 1;
        int T = target * 2;
        int l = 0;
        List<int[]> ans = new ArrayList<>();
        for (int r = right; r > 1; r--) {
            l = r - 1;
            while (l >= 1 && l < r) {
                int len = r - l + 1;
                int mul = len * (l + r);
                if (mul >= T) {
                    if (mul == T) {
                        ans.add(build(l, r));
                    }
                    break;
                } else {
                    l--;
                }
            }
        }
        Collections.reverse(ans);
        return ans.toArray(new int[ans.size()][]);
    }

    private static int[] build(int start, int end) {
        int n = end - start + 1;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = start + i;
        }
        return ans;
    }

    public static List<Integer> findAnagrams(String s, String p) {
        if (s == null || s.length() == 0 || p == null || s.length() < p.length()) {
            return new ArrayList<>();
        }
        int[] map = new int[26];
        char[] cs = s.toCharArray();
        char[] ps = p.toCharArray();
        for (char c : ps) {
            map[c - 'a']++;
        }
        int n = cs.length, m = ps.length, l = 0, r = 0, cnt = 0;
        List<Integer> ans = new ArrayList<>();
        for (; l < n; l++) {
            while (r < n && cnt < m) {
                map[cs[r] - 'a']--;
                if (map[cs[r] - 'a'] >= 0) {
                    cnt++;
                }
                r++;
            }
            if (cnt == m && r - l == m) {
                ans.add(l);
            }
            map[cs[l] - 'a']++;
            if (map[cs[l] - 'a'] > 0) {
                cnt--;
            }
        }
        return ans;
    }

    private static boolean check(int[] map) {
        for (int i = 0; i < 26; i++) {
            if (map[i] > 0) {
                return false;
            }
        }
        return true;
    }

    public static int characterReplacement(String s, int k) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] map = new int[26];
        char[] cs = s.toCharArray();
        for (char c : cs) {
            map[c - 'A']++;
        }
        int ans = 0, n = cs.length;
        for (int i = 0; i < 26; i++) {
            if (map[i] == 0) {
                continue;
            }
            char c = (char) ('A' + i);
            int cnt = 0, l = 0, r = 0;

            for (; r < n; r++) {
                if (cs[r] != c) {
                    cnt++;
                }
                while (cnt > k) {
                    ans = Math.max(ans, r - l);
                    if (cs[l] != c && cnt > 0) {
                        cnt--;
                    }
                    l++;
                }
            }
            ans = Math.max(ans, r - l);
        }
        return ans;
    }

    public static int maxRepOpt1(String text) {
        if (text == null) {
            return 0;
        }
        if (text.length() <= 1) {
            return text.length();
        }
        int[] map = new int[26];
        char[] cs = text.toCharArray();
        int ans = 0, cnt = 1, n = cs.length;
        char tc = cs[0];
        for (char c : cs) {
            map[c - 'a']++;
        }
        for (int i = 1; i < n; i++) {
            if (cs[i] == tc) {
                cnt++;
            } else {
                int secIdx = i + 1;
                while (secIdx < n && cs[secIdx] == tc) {
                    secIdx++;
                    cnt++;
                }
                if (map[tc - 'a'] > cnt) {
                    cnt += 1;
                }
                ans = Math.max(ans, cnt);

                cnt = 1;
                tc = cs[i];
            }
        }

        if (map[tc - 'a'] > cnt) {
            cnt += 1;
        }
        ans = Math.max(ans, cnt);

        return ans;
    }

    public static int longestNiceSubarray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int ans = 0, l = 0, r = 0, or = 0, n = nums.length;
        for (; l < n; l++) {
            while (l <= r && r < n && (or & nums[r]) == 0) { // 没有交集
                or |= nums[r];  // 把集合 nums[right] 并入 or 中
                r++;
            }
            ans = Math.max(ans, r - l);
            or ^= nums[l]; // 从 or 中去掉集合 nums[left]
        }
        return ans;
    }

    public static int subarraysWithKDistinct(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return 0;
        }
        return helper4(nums, k) - helper4(nums, k + 1);
    }

    private static int helper4(int[] nums, int k) {
        int ans = 0, l = 0, r = 0, cnt = 0, n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (; r < nums.length; r++) {
            Integer vc = map.getOrDefault(nums[r], 0);
            if (vc == 0) {
                cnt++;
            }
            map.put(nums[r], vc + 1);
            while (cnt >= k) {
                ans += n - r;
                Integer vc2 = map.get(nums[l]);
                if (vc2 == 1) {
                    cnt--;
                }
                map.put(nums[l], vc2 - 1);
                l++;
            }
        }
        return ans;
    }

    public static long countOfSubstrings(String word, int k) {
        if (word == null || word.length() < k) {
            return 0;
        }
        return helper3(word.toCharArray(), k) - helper3(word.toCharArray(), k + 1);
    }

    static Set<Character> set = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));

    private static boolean hasAllVowel(int[] map) {
        return map['a' - 'a'] > 0 && map['e' - 'a'] > 0 && map['i' - 'a'] > 0 && map['o' - 'a'] > 0 && map['u' - 'a'] > 0;
    }

    public static long helper3(char[] cw, int k) {
        long ans = 0;
        int n = cw.length, l = 0, r = 0, cnt = 0, cnt2 = 0;
        int[] map = new int[26];
        for (; r < n; r++) {
            char c = cw[r];
            if (set.contains(c)) {
                map[c - 'a']++;
            } else {
                cnt++;
            }
            while (cnt >= k && hasAllVowel(map)) {
                ans += n - r;
                char c2 = cw[l];
                if (set.contains(c2)) {
                    map[c2 - 'a']--;
                } else {
                    cnt--;
                }
                l++;
            }
        }
        return ans;
    }

    public static int numberOfSubarrays(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return 0;
        }
        return helper2(nums, k) - helper2(nums, k + 1);
    }

    public static int helper2(int[] nums, int k) {
        int ans = 0, n = nums.length, l = 0, r = 0, cnt = 0;
        for (; r < n; r++) {
            cnt += ((nums[r] & 1) == 1) ? 1 : 0;
            while (cnt >= k) {
                ans += n - r;
                cnt -= ((nums[l] & 1) == 1) ? 1 : 0;
                l++;
            }
        }
        return ans;
    }

    public static int numSubarraysWithSum(int[] nums, int goal) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        return helper(nums, goal) - helper(nums, goal + 1);
    }

    public static int helper(int[] nums, int goal) {
        int ans = 0, n = nums.length, l = 0, r = 0, sum = 0;
        for (; r < n; r++) {
            sum += nums[r];
            while (l <= r && sum >= goal) {
                ans += n - r;
                sum -= nums[l];
                l++;
            }
        }
        return ans;
    }

    public static long validSubstringCount(String word1, String word2) {
        if (word1 == null || word1.length() == 0 || word2 == null || word2.length() == 0 || word1.length() < word2.length()) {
            return 0;
        }
        int n = word1.length(), m = word2.length(), l = 0, r = 0, cnt = 0;
        int[] map = new int[26];
        long ans = 0;
        for (char c : word2.toCharArray()) {
            map[c - 'a']++;
        }

        for (; r < n; r++) {
            char c = word1.charAt(r);
            map[c - 'a']--;
            if (map[c - 'a'] >= 0) {
                cnt++;
            }
            while (cnt >= m) {
                ans += n - r;
                c = word1.charAt(l);
                map[c - 'a']++;
                if (map[c - 'a'] > 0) {
                    cnt--;
                }
                l++;
            }
        }

        return ans;
    }

    public static long countGood(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length, l = 0, r = 0, cnt = 0;
        long ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (; r < n; r++) {
            Integer i = map.get(nums[r]);
            if (i == null) {
                map.put(nums[r], 1);
            } else {
                map.put(nums[r], i + 1);
                if (i > 0) {
                    cnt += i;
                }
            }
            while (cnt >= k) {
                ans += n - r;
                Integer i1 = map.get(nums[l]);
                if (i1 != null && i1 >= 2) {
                    cnt -= i1 - 1;
                }
                map.put(nums[l], i1 - 1);
                l++;
            }
        }
        return ans;
    }

    public static int countCompleteSubarrays(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int ans = 0, l = 0, r = 0, n = nums.length, cnt = 0;
        int[] map = new int[2005];
        for (; r < n; r++) {
            if (map[nums[r]] == 0) {
                cnt++;
            }
            map[nums[r]]++;
            while (cnt >= set.size()) {
                ans += n - r;
                map[nums[l]]--;
                if (map[nums[l]] == 0) {
                    cnt--;
                }
                l++;
            }
        }
        return ans;
    }

    public static int numberOfSubstrings(String s, int k) {
        if (s == null || s.length() < k) {
            return 0;
        }
        char[] cs = s.toCharArray();
        int n = cs.length, ans = 0, l = 0, r = 0;
        int[] map = new int[26];
        for (; r < n; r++) {
            map[cs[r] - 'a']++;
            while (map[cs[r] - 'a'] >= k) {
                ans += n - r;
                map[cs[l] - 'a']--;
                l++;
            }
        }
        return ans;
    }

    public static long countSubarrays(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return 0;
        }
        int maxNum = Arrays.stream(nums).max().getAsInt();
        int l = 0, r = 0, n = nums.length, cnt = 0;
        long ans = 0;
        for (; r < n; r++) {
            if (nums[r] == maxNum) {
                cnt++;
            }
            while (cnt >= k) {
                ans += n - r;
                if (nums[l] == maxNum) {
                    cnt--;
                }
                l++;
            }
        }
        return ans;
    }

    public static int numberOfSubstrings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int n = s.length(), l = 0, r = 0, ans = 0;
        char[] cs = s.toCharArray();
        int[] map = new int[3];
        for (; r < n; r++) {
            map[cs[r] - 'a']++;
            while (map[0] > 0 && map[1] > 0 && map[2] > 0) {
                ans += n - r;
                map[cs[l++] - 'a']--;
            }
        }
        return ans;
    }

    public static int beautifulBouquet(int[] flowers, int cnt) {
        if (flowers == null || flowers.length == 0) {
            return 0;
        }
        Arrays.fill(map, 0);

        int n = flowers.length, l = 0, r = 0;
        long ans = 0;
        for (; r < n; r++) {
            map[flowers[r]]++;
            while (map[flowers[r]] > cnt) {
                map[flowers[l]]--;
                l++;
            }
            ans += r - l + 1;
        }
        return (int) ans % 1000000007;

    }

    public static int[] map = new int[100000];

    public static long continuousSubarrays(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Deque<Integer> increStack = new LinkedList<>(); // 获取最小值
        Deque<Integer> decreStack = new LinkedList<>(); // 获取最大值
        long ans = 0;
        int n = nums.length, l = 0, r = 0;
        for (; r < n; r++) {
            addIncre(decreStack, nums, r);
            addDecr(increStack, nums, r);
            while (nums[decreStack.getFirst()] - nums[increStack.getFirst()] > 2) {
                removeFirst(increStack, l);
                removeFirst(decreStack, l);
                l++;
            }
            ans += r - l + 1;
        }
        return ans;
    }

    private static void removeFirst(Deque<Integer> stack, Integer idx) {
        while (!stack.isEmpty() && stack.peekFirst() <= idx) {
            stack.pollFirst();
        }
    }

    private static void addIncre(Deque<Integer> stack, int[] nums, Integer idx) {
        while (!stack.isEmpty() && nums[stack.peekLast()] <= nums[idx]) {
            stack.pollLast();
        }
        stack.addLast(idx);
    }

    private static void addDecr(Deque<Integer> stack, int[] nums, Integer idx) {
        while (!stack.isEmpty() && nums[stack.peekLast()] >= nums[idx]) {
            stack.pollLast();
        }
        stack.addLast(idx);
    }

    public static long countSubarrays(int[] nums, long k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int l = 0, r = 0, n = nums.length;
        long ans = 0, sum = 0L;
        for (; r < n; r++) {
            sum += nums[r];
            while (sum * (r - l + 1) >= k) {
                sum -= nums[l++];
            }
            ans += r - l + 1;
        }
        return ans;
    }

    public static int countKConstraintSubstrings(String s, int k) {
        if (s == null || s.length() < k) {
            return 0;
        }
        char[] cs = s.toCharArray();
        int[] map = new int[2];
        int ans = 0, l = 0, r = 0, n = cs.length, cnt = 0;
        for (; r < n; r++) {
            map[cs[r] - '0']++;
            while (map[1] > k && map[0] > k) {
                map[cs[l++] - '0']--;
            }
            ans += r - l + 1;
        }

        /*for(; l < n; l ++){
            while(l <= r && r < n && cnt < 2 * k){
                if(map[cs[r]] < k){
                    map[cs[r]]++;
                    cnt++;
                    r++;
                }else{
                    break;
                }
            }
            if(cnt == 2 * k) {
                ans += r - l;
                map[cs[l]]--;
                cnt --;
            }
        }*/
        return ans;
    }

    public static int numSubarrayProductLessThanK(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 1) {
            return 0;
        }
        int ans = 0;
        int n = nums.length;
        int prod = 1;
        int l = 0;
        for (int r = 0; r < n; r++) {
            prod *= nums[r];
            while (prod >= k) {
                prod /= nums[l++];
            }
            ans += r - l + 1;
        }
        return ans;
    }

    public static int numSubarrayProductLessThanK2(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return 0;
        }
        int ans = 0, l = 0, r = 0, n = nums.length;
        int mul = 1;
        for (; r < n; r++) {
            mul *= nums[r];
            while (mul >= k) {
                mul /= nums[l];
                l++;
            }
            ans += (r - l + 1);
        }
        return ans;
    }

    public static String minWindow(String s, String t) {
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }
        int[] map = new int[256];
        int n = s.length(), m = t.length(), cnt = 0;
        for (char c : t.toCharArray()) {
            map[c]++;
        }
        int l = 0, r = 0;
        int resL = 0, resR = n + 1;
        char[] cs = s.toCharArray();
        for (; l < n; l++) {
            while (l <= r && r < n && cnt < m) {
                map[cs[r]]--;
                if (map[cs[r]] >= 0) {
                    cnt++;
                }
                r++;
            }
            if (cnt >= m) {
                if ((resR - resL) > (r - l)) {
                    resR = r;
                    resL = l;
                }
            }
            map[cs[l]]++;
            if (map[cs[l]] > 0) {
                cnt--;
            }
        }
        return resR == (cs.length + 1) ? "" : s.substring(resL, resR);
    }

    public static int minSizeSubarray(int[] nums, int target) {
        long total = 0;
        for (int num : nums) {
            total += num;
        }
        int n = nums.length, N = 2 * n;

        long t = target % total, sum = 0;
        int l = 0, r = 0, ans = Integer.MAX_VALUE;
        for (; l < N; l++) {
            while (l <= r && r < N && sum < t) {
                sum += nums[r % n];
                r++;
            }
            if (sum == t) {
                ans = Math.min(ans, r - l);
            }
            sum -= nums[l % n];
        }

        return ans == Integer.MAX_VALUE ? -1 : ans + (int) (target / total) * n;
    }

    public static int balancedString(String s) {
        if (s == null || s.length() == 0 || s.length() % 4 != 0) {
            return 0;
        }
        char[] cs = s.toCharArray();
        int n = s.length(), ans = n;
        int[] map = new int['X'];
        for (char c : cs) {
            map[c]++;
        }
        int avg = n / 4;
        int l = 0, r = 0;
        for (; l < n; l++) {
            while (l <= r && r < n && !check(map, avg)) {
                map[cs[r]]--;
                r++;
            }
            if (check(map, avg)) {
                ans = Math.min(ans, r - l);
            }
            map[cs[l]]++;
        }
        return ans;
    }

    private static boolean check(int[] map, int avg) {
        return map['Q'] <= avg && map['W'] <= avg && map['E'] <= avg && map['R'] <= avg;
    }

    public static String shortestBeautifulSubstring(String s, int k) {
        if (s == null || s.length() < k) {
            return "";
        }
        char[] cs = s.toCharArray();
        String cur = null;
        int n = cs.length, cnt = 0, sum = 0;
        int l = 0, r = 0;
        for (; l < n; l++) {
            while (r < n && cnt < k) {
                if (cs[r] == '1') {
                    cnt++;
                }
                sum += cs[r];
                r++;
            }
            if (cnt == k) {
                if (cur == null || cur.length() > r - l) {
                    cur = s.substring(l, r);
                } else if (cur.length() == r - l) {
                    if (cur.compareTo(s.substring(l, r)) > 0) {
                        cur = s.substring(l, r);
                    }
                }
            }
            if (cs[l] == '1') {
                cnt--;
            }
            sum -= cs[l];
        }
        return cur == null ? "" : cur;
    }

//    private int

    public static int minSubArrayLen(int target, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int l = 0, r = 0, sum = 0, ans = n + 1;
        for (; l < n; l++) {
            while (r < n && sum + nums[r] < target) {
                sum += nums[r];
                r++;
            }
            if (sum >= target) {
                ans = Math.min(ans, r - l);
            }
            sum -= nums[l];
        }
        return ans > n ? 0 : ans;
    }

    public static int minOperations(int[] nums, int x) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int target = -x;
        for (int num : nums) {
            target += num;
        }
        if (target < 0) {
            return -1;
        }
        int l = 0, r = 0, n = nums.length, sum = 0, ans = -1;
        for (; l < n; l++) {
            while (r < n && sum + nums[r] <= target) {
                sum += nums[r];
                r++;
            }
            if (sum == target) {
                ans = Math.max(ans, r - l);
            }
            sum -= nums[l];
        }
        return ans < 0 ? -1 : n - ans;
    }

    public static int longestOnes(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return 0;
        }
        int n = nums.length, ans = 0;
        int l = 0, r = 0, cnt = 0;
        for (; l < n; l++) {
            while (r < n && cnt <= k) {
                if (cnt == k && nums[r] == 0) {
                    break;
                }
                if (nums[r] == 0) {
                    cnt += 1;
                }
                r++;
            }

            ans = Math.max(ans, r - l);
            if (nums[l] == 0) {
                cnt -= 1;
            }
        }
        return ans;
    }

    public static int maxSubarrayLength(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return 0;
        }
        int n = nums.length, ans = 0;
        int l = 0, r = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (; l < n; l++) {
            while (r < n && map.getOrDefault(nums[r], 0) < k) {
                map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);
                r++;
            }
            ans = Math.max(ans, r - l);
            if (map.containsKey(nums[l])) {
                map.put(nums[l], map.get(nums[l]) - 1);
            }
        }
        return ans;
    }

    public static int maximumUniqueSubarray(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return 0;
        }
        int n = nums.length, ans = 0, sum = 0;
        int l = 0, r = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (; l < n; l++) {
            while (r < n && !map.containsKey(nums[r])) {
                map.put(nums[r], r);
                sum += nums[r];
                r++;
            }
            ans = Math.max(ans, sum);
            if (map.containsKey(nums[l])) {
                map.remove(nums[l]);
                sum -= nums[l];
            }
        }
        return ans;
    }

    public static int totalFruit(int[] fruits) {
        if (fruits == null || fruits.length <= 0) {
            return 0;
        }
        int n = fruits.length;
        int[] map = new int[10005];
        int cnt = 0, l = 0, r = 0, ans = 0;
        for (; l < n; l++) {
            while (r < n && cnt <= 2) {
                if (map[fruits[r]] == 0) {
                    if (cnt + 1 > 2) {
                        break;
                    }
                    cnt++;
                }
                map[fruits[r]]++;
                r++;
            }
            map[fruits[l]]--;
            if (cnt <= 2) {
                ans = Math.max(ans, r - l);
                if (map[fruits[l]] == 0) {
                    cnt--;
                }
            }

        }
        return ans;

    }

    public static int equalSubstring(String s, String t, int maxCost) {
        if (s == null || t == null || s.length() != t.length()) {
            return 0;
        }
        int l = 0, r = 0, n = s.length();
        int[] dif = new int[n];
        for (int i = 0; i < n; i++) {
            dif[i] = Math.abs(s.charAt(i) - t.charAt(i));
        }
        int cnt = 0, ans = 0;
        for (; l < n; l++) {
            while (r < n && cnt + dif[r] <= maxCost) {
                cnt += dif[r];
                r++;
            }
            if (cnt >= 0) {
                if (cnt <= maxCost) ans = Math.max(ans, r - l);
                cnt -= dif[l];
            }
        }
        return ans;
    }

    public static int minRemoval(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int n = nums.length, l = 0, r = 0;
        int ans = 0;
        for (; l < n; l++) {
            while (l <= r && r < n && nums[l] * k >= nums[r]) {
                r++;
            }
            ans = Math.max(ans, r - l);
        }
        return n - ans;
    }

    public static int longestSubarray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len1 = 0, len2 = 0;
        int cnt = 0;
        int ans = 0;
        int l = 0, r = 0, n = nums.length;
        for (; l < n; l++) {
            while (l <= r && r < n && cnt < 2) {
                if (nums[r] == 0) cnt++;
                r++;
            }
            ans = Math.max(ans, r - l - cnt);
            if (nums[l] == 0) {
                cnt--;
            }
        }
        return ans == n ? ans - 1 : ans;
    }

    public static int maximumLengthSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int l = 0, r = 0, n = s.length();
        int ans = 0;
        int[] map = new int[26];
        char[] cs = s.toCharArray();
        for (; l < n; l++) {
            while (l <= r && r < n && map[cs[r] - 'a'] < 2) {
                map[cs[r] - 'a']++;
                r++;
            }
            ans = Math.max(ans, r - l);
            map[cs[l] - 'a']--;
        }
        return ans;
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int l = 0, r = 0, n = s.length();
        int ans = 0;
        int[] map = new int[256];
        char c = ' ';
        for (; l < n; l++) {
            while (l <= r && r < n && map[s.charAt(r)] == 0) {
                map[s.charAt(r)]++;
                r++;
            }
            ans = Math.max(ans, r - l);
            map[s.charAt(l)]--;
        }
        return ans;
    }

    public static int maxScore(int[] cardPoints, int k) {
        if (cardPoints == null || cardPoints.length < k) {
            return 0;
        }
        int sum = 0, ans = 0;
        int n = cardPoints.length;
        for (int i = k - 1; i >= 0; i--) {
            sum += cardPoints[i];
        }
        ans = sum;
        int l = k - 1, r = n - 1;
        for (int i = 0; i < k; i++) {
            sum -= cardPoints[l];
            sum += cardPoints[r];
            l--;
            r--;
            ans = Math.max(ans, sum);
        }
        return ans;
    }

    public long maximumSubarraySum(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return -1;
        }
        long ans = 0, sum = 0;
        Map<Integer, Integer> set = new HashMap<>();
        for (int i = 0; i < k; i++) {
            sum += nums[i];
            set.merge(nums[i], 1, Integer::sum);
        }
        if (set.size() == k) {
            ans = sum;
        }
        for (int i = k; i < nums.length; i++) {
            sum -= nums[i - k];
            sum += nums[i];
            set.merge(nums[i - k], 1, (a, b) -> a - b);
            if (set.get(nums[i - k]) <= 0) {
                set.remove(nums[i - k]);
            }
            set.merge(nums[i], 1, Integer::sum);
            if (set.size() == k) {
                ans = Math.max(ans, sum);
            }
        }
        return ans;
    }


    public static long maxSum(List<Integer> nums, int m, int k) {
        if (nums == null || nums.size() < m || k <= 0) {
            return -1;
        }
        long ans = 0, sum = 0;
        Map<Integer, Integer> set = new HashMap<>();
        for (int i = 0; i < k; i++) {
            sum += nums.get(i);
            set.merge(nums.get(i), 1, Integer::sum);
//            set.merge(nums.get(i), 1, (a, b) -> a - b);
        }
        if (set.size() >= m) {
            ans = sum;
        }
        for (int i = k; i < nums.size(); i++) {
            sum -= nums.get(i - k);
            sum += nums.get(i);
            set.merge(nums.get(i - k), 1, (a, b) -> a - b);
            if (set.get(nums.get(i - k)) <= 0) {
                set.remove(nums.get(i - k));
            }
            set.merge(nums.get(i), 1, Integer::sum);
            if (set.size() >= m) {
                ans = Math.max(ans, sum);
            }
        }
        return ans;
    }

    public static int[] getAverages(int[] nums, int k) {
        if (nums == null) {
            return new int[0];
        }
        if (nums.length < 2 * k + 1) {
            int[] ans = new int[nums.length];
            Arrays.fill(ans, -1);
            return ans;
        }
        int n = nums.length;
        int[] ans = new int[n];
        long sum = 0, K = 2 * k + 1;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
            ans[i] = -1;
        }
        for (int i = n - 1; i > k; i--) {
            ans[i] = -1;
        }
        for (int i = k; i < K; i++) {
            sum += nums[i];
        }
        ans[k] = (int) (sum / K);
        for (int i = k + 1; i < n - k; i++) {
            sum -= nums[i - k - 1];
            sum += nums[i + k];
            ans[i] = (int) (sum / K);
        }
        return ans;
    }

    public static int minimumRecolors(String blocks, int k) {
        if (blocks == null || blocks.length() < k) {
            return 0;
        }
        int n = blocks.length();
        int cnt = 0, ans = 0;
        for (int i = 0; i < k; i++) {
            if (blocks.charAt(i) == 'W') {
                cnt++;
            }
        }
        ans = cnt;
        for (int i = k; i < n; i++) {
            if (blocks.charAt(i) == 'W') {
                cnt++;
            }
            if (blocks.charAt(i - k) == 'B') {
                cnt--;
            }
            ans = Math.min(ans, cnt);
        }
        return ans;
    }

    public static int numOfSubarrays(int[] arr, int k, int threshold) {
        if (arr == null || arr.length < k) {
            return 0;
        }
        int n = arr.length;
        int sum = 0, cnt = 0;
        threshold *= k;
        for (int i = 0; i < k; i++) {
            sum += arr[i];
        }
        if (sum >= threshold) {
            cnt++;
        }
        for (int i = k; i < n; i++) {
            sum += arr[i] - arr[i - k];
            if (sum >= threshold) {
                cnt++;
            }
        }
        return cnt;
    }

    public static double findMaxAverage(int[] nums, int k) {

        int sum = 0;
        int ans = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        ans = sum;
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - nums[i - k];
            ans = Math.max(ans, sum);
        }
        return ans * 1.0 / k;
    }

    public static int maxVowels2(String s, int k) {
        int n = s.length();
        int vowel_count = 0;
        for (int i = 0; i < k; ++i) {
            vowel_count += isVowel(s.charAt(i));
        }
        int ans = vowel_count;
        for (int i = k; i < n; ++i) {
            vowel_count += isVowel(s.charAt(i)) - isVowel(s.charAt(i - k));
            ans = Math.max(ans, vowel_count);
        }
        return ans;
    }

    public static int isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
    }


    public static int maxVowels(String s, int k) {
        if (s == null || s.length() == 0 || k <= 0) {
            return 0;
        }
        int ans = 0;
        int left = 0, right = 0, n = s.length();
        int cnt = 0;
        char c = ' ';
        for (; left < k; left++) {
            c = s.charAt(left);
            if (vowelSet.contains(c)) {
                cnt++;
            }
        }
        ans = cnt;
        right = left;
//        n -= k;
        for (; left < n; left++) {
            c = s.charAt(left);
            if (vowelSet.contains(c)) {
                cnt++;
            }
            c = s.charAt(left - k);
            if (vowelSet.contains(c)) {
                cnt--;
            }
            ans = Math.max(ans, cnt);
        }
        return ans;
    }

    static Set<Character> vowelSet = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));

    public static String removeDuplicates(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        Deque<Character> q = new LinkedList<>();
        int i = 0, n = s.length();
        while (i < n) {
            if (i + 1 < n && s.charAt(i) == s.charAt(i + 1)) {
                i = i + 2;
            } else {
                if (!q.isEmpty() && q.peekLast() == s.charAt(i)) {
                    q.pollLast();
                } else {
                    q.add(s.charAt(i));
                }
                i++;
            }
        }
        return q.stream().map(String::valueOf).collect(Collectors.joining());
    }

    static class RecentCounter {

        Deque<Integer> q = new LinkedList<>();

        public RecentCounter() {
        }

        public int ping(int t) {
            q.add(t);
            while (!q.isEmpty() && q.peek() < t - 3000) {
                q.poll();
            }
            return q.size();
        }
    }

    static class RecentCounter_2 {

        List<Integer> list = null;

        public RecentCounter_2() {
            list = new ArrayList<>(5000);
        }

        public int ping(int t) {
            list.add(t);
            t -= 3000;
            int size = list.size();
            int left = 0, right = size - 1;
            while (left + 1 < right) {
                int mid = (left + right) / 2;
                Integer val = list.get(mid);
                if (val == t) {
                    return right - mid + 1;
                } else if (val < t) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            if (list.get(left) >= t) {
                return size - left;
            }
            if (list.get(right) >= t) {
                return size - right;
            }
            return size - right - 1;
        }
    }

    public static int countStudents(int[] students, int[] sandwiches) {
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < students.length; i++) {
            q.add(students[i]);
        }
        for (int s : sandwiches) {
            int size = q.size();
            int cnt = 0;
            while (!q.isEmpty()) {
                int stu = q.poll();
                if (stu != s) {
                    q.add(stu);
                    cnt++;
                    if (cnt == size) {
                        return q.size();
                    }
                } else {
                    break;
                }
            }
        }
        return q.size();
    }

    public static int countStudents_ii(int[] students, int[] sandwiches) {
        int[] cnt = new int[2];
        for (int s : students) {
            cnt[s]++;
        }
        for (int s : sandwiches) {
            if (cnt[s] == 0) break;
            cnt[s]--;
        }
        return cnt[0] + cnt[1];
    }

    public static int maximumGain(String s, int x, int y) {
        // x ab
        // y ba
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (y > x) {
            int temp = x;
            x = y;
            y = temp;
            s = s.replace("a", "#").replace("b", "a").replace("#", "b");
        }
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            int cntA = 0, cntB = 0;
            while (i < s.length() && (s.charAt(i) == 'a' || s.charAt(i) == 'b')) {
                char c = s.charAt(i++);
                if (c == 'a') {
                    cntA++;
                } else {
                    if (cntA > 0) {
                        cntA--;
                        ans += x;
                    } else {
                        cntB++;
                    }
                }
            }
            ans += Math.min(cntA, cntB) * y;
        }
        return ans;
    }


    public static int minOperations(String[] logs) {
        if (logs == null || logs.length == 0) {
            return 0;
        }
        int ans = 0;
        Deque<String> stack = new LinkedList<>();
        for (String log : logs) {
            if (log.equals("./")) {
            } else if (log.equals("../")) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                stack.push(log);
            }
        }
        return stack.size();
    }

    public static String removeDuplicates(String s, int k) {
        if (s == null || s.length() == 0) {
            return "";
        }
        Deque<Integer> stack = new LinkedList<>();
        StringBuilder sb = new StringBuilder(s);
        for (int i = 0; i < sb.length(); i++) {
            if (i == 0 || sb.charAt(i) != sb.charAt(i - 1)) {
                stack.push(1);
            } else {
                int incr = stack.pop() + 1;
                if (incr == k) {
                    sb.delete(i - k + 1, i + 1);
                    i = i - k;
                } else {
                    stack.push(incr);
                }
            }
        }
        return sb.toString();

    }


    public static int[] asteroidCollision(int[] asteroids) {
        if (asteroids == null || asteroids.length == 0) {
            return new int[0];
        }
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < asteroids.length; i++) {
            int a = asteroids[i];
            boolean alive = true;
            while (alive && !stack.isEmpty() && a < 0 && stack.peek() > 0) {
                alive = stack.peek() < a * -1;
                if (stack.peek() <= a * -1) {
                    stack.pop();
                }
            }
            if (alive) {
                stack.push(a);
            }
        }
        ArrayList<Integer> list = new ArrayList<>(stack);
        Collections.reverse(list);
        return list.stream().mapToInt(i -> i).toArray();
    }


    public static String removeKdigits(String num, int k) {
        if (num == null || num.length() == 0 || num.length() <= k) {
            return "0";
        }
        Deque<Character> stack = new LinkedList<>();
        for (int i = 0; i < num.length(); i++) {
            while (!stack.isEmpty() && k > 0 && stack.peek() > num.charAt(i)) {
                stack.pop();
                k--;
            }
            stack.push(num.charAt(i));
        }
        while (!stack.isEmpty() && k > 0) {
            stack.pop();
            k--;
        }
        StringBuilder sb = new StringBuilder();
        boolean skipStartZero = true;
        while (!stack.isEmpty()) {
            Character c = stack.pollLast();
            if (skipStartZero && c == '0') {
                continue;
            } else {
                skipStartZero = false;
            }
            sb.append(c);
        }

        return sb.length() == 0 ? "0" : sb.toString();
    }

    public static int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        int ans = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        for (int i = 1; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int low = height[stack.pop()];
                if (!stack.isEmpty()) {
                    int width = i - stack.peek() - 1;
                    int hei = Math.min(height[stack.peek()], height[i]);
                    ans += width * (hei - low);
                }
            }
            stack.push(i);
        }
        return ans;
    }

    public static int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        int ans = 0;
        for (int i = 0; i < heights.length; i++) {
            while (stack.size() > 1 && heights[stack.peek()] >= heights[i]) {
                int hei = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                ans = Math.max(ans, hei * width);
            }
            stack.push(i);
        }
        while (stack.size() > 1) {
            int hei = heights[stack.pop()];
            int width = heights.length - stack.peek() - 1;
            ans = Math.max(ans, hei * width);
        }
        return ans;
    }

}